\chapter{Conversion in Object Oriented Programming Languages} %% Modelling Conversions ???
There are various concepts that deal with conversion in object oriented programming
languages, however those concepts may slightly vary from language to language. It is of 
interest to look at the paradigms suggested by the used programming language, especially 
when a library is to be developped. In this case, the use of standard concepts might
terifically simplify the use of such a library to third parties. Not only will Programmers find
libraries base on common concepts more intuitively to use but also will the
documentation be easier to write and to read because along with standard concepts there
has often also evolved a commonly  understood vocabulary.
Since the conversion library is to be written in C++, this chapter is focusing on
the concepts provided by C++.

First of all the term \emph{conversion} should be clearly defined. A conversion is
considered to be procedure, accepting an object of type \emph{A} as input and returning 
an object of type \emph{B}, if both types, \emph{A} and \emph{B} describe the same
entity. Ideally the \emph{source type} \emph{A} and  the \emph{target type}
\emph{B} of a conversion contain exactly the same information on the entity, they
describe. 
For  the case of geometric data, this means that the \emph{source type} and the \emph{target
type} both describe the same geometric entity.

Doubtlessly, a \emph{type} is supposed to be represented by a class in all object 
oriented languages. In C++ there are two common ways to neatly model conversions.
The first and probably most spread is the use of \emph{constructors}.

\subsection{Modelling Conversions as Constructors}
Constructors may be used to implement conversions. In this case the conversion 
procedure is implemented within a constructor of the \emph{target class}. Such a 
Constructor will accept an Instance of the \emph{source class} as argument and in 
some cases further arguments. The additional arguments might be considered as options
passed to the conversion procedure.

The skeleton of conversion from the \emph{source class A} to the \emph{target class B}
would thus look as follows.
\lstinputlisting{code/ConversionConstructor.cpp}

The conversion could then be used as listed below. 

\lstinputlisting{code/ConversionConstructorUsage.cpp}

\subsection{Conversion Operator}
Alternatively, C++ offers the possibility of defining operators. In order
to implement a conversion from the \emph{source class A} to the \emph{target class B}     
a conversion operator would look as in the example below.

\lstinputlisting{code/ConversionOperator.cpp}

The real power of operators shows up when there is a need to call them. Most operators
are very handy to call, conversion operators however are probably the simplest operators
at all, when it is about to call them. In most of the cases conversion operators don't
have to be called at all. Frequently the call to the conversion operator is done
automatically by the compiler as shown in the following example.

\lstinputlisting{code/ConversionOperatorUsage.cpp}

In some cases the conversion operator needs to be called expicitly. This can be reached
by using explicit type casting, as shown below.

\lstinputlisting{code/ConversionOperatorExplicit.cpp}

\subsection{Comparison of the two Constructs}

Conversion constructors allow for implementing conversions within the \emph{target class},
while conversion operators are implemented within the \emph{source class}. This makes
the use of conversion constructors more convenient, when the \emph{source class} has
been implemented by a third party and inversely. If the \emph{target class} is provided
by a third party and should not be touched, conversion constructors could still be
used by simply deriving a sub class from that \emph{target class}. Alike, sub classing
can be employed if the \emph{source class} is untouchable and conversion operators are
preferred.

\section{An Infrastructure for Conversion}

The constructs provided by C++ offer only a rather rudimentary functionality. While
they doubtlessly make the programmers everyday life  much easier, they leak some features
which might be extremely helpful within a framework specialized in converting. Such a 
desirable feature would be the ability of an automated chaining of conversion as it is
required.

\subsection{Chaining}
By chaining of conversions it is meant to execute two or more of the available conversions
one after another in order to get to the desired data type. In a simple example we
had a conversion from A to B, as well as one able to convert from B to C. A direct
conversion form A to C would however be missing. The situation is depicted in figure \ref{fig:conversion_chain}.
In this case a conversion from A to C could still be achieved by converting from A to B
and then appending another conversion from B to C.

\begin{figure}[!ht]
    \begin{center}
        \includegraphics[scale=0.5]{figures/chain.png}
        \caption{A very simple conversion chain.}
        \label{fig:conversion_chain}
    \end{center}
\end{figure}


\subsection{Conversion Graphs}

If more types and more conversions are involved than in the case discussed above, 
it might be possible that more than one way exists to reach a target type from a
source type. It might then become a little bit tricky not only to decide which way is the 
best one but already the seemingly simple task of determining and listing all existing paths from
the source type to the target type might be an issue.

It is very helpful to note that such situations as depicted in figure \ref{fig:conversion_chain}
or in figure \ref{fig:conversion_graph} can be considered as directed graphs, since many 
efficient algorithms have been developed in conjunction with path finding in directed graphs.


\begin{figure}[!ht]
    \begin{center}
        \includegraphics[scale=0.5]{figures/conversionGraph.png}
        \caption{A very simple conversion graph.}
        \label{fig:conversion_graph}
    \end{center}
\end{figure}

\subsection{Edge Weights}
In those graphs types are represented by vertices and conversions correspond to 
edges. It is possible to engage algorithms which find shortest paths in order to find
good conversion chains by assigning weights to the Edges. To achieve this ,
the Edge weight is set to a value quantifying the quality of a conversion such that
high values stand for conversions of low quality whereas low edge weights stand for
good conversions. The edge weight is thus a measure for the loss of a conversion.
To give an example, the edges in the graph depicted in figure
\ref{fig:conversion_graph} have been assigned edge weights.

In the \emph{shortest path problem} as it is solved by the algorithms presented below, 
the length of a path is retrieved by summing up the weights of all edges contained in the path.
\footnote{Since shortest paths will newer contain loops, paths containing loops are not of interest in this context. Therefore each edge contained in all of the paths will only be passed once.}
Once, the edge weights are assigned, the problem of finding the shortest path in a graph becomes equivalent to the problem
of finding the best conversion, assuming that the accumulation of the losses caused by each conversions of a conversion
chain equals the loss of the entire conversion chain.

This is of course not completely true. Whenever the loss of information of two conversions
in the conversion chain has overlapping chunks of information, the loss of the conversion chain is actually smaller
than the accumulated loss. In most cases however, the loss of a conversion is due to the 
inability of the \emph{target type} to represent certain chunks of information. If the \emph{target type}
is unable to represent those chunks of information, there will be no conversions having this type as 
\emph{source type} which will loose the same information again. This states a reason, why the loss
of information can be considered as approximately cumulative at least for conversion chains containing
only two conversions.

\subsubsection{Quantifying the Edge Weights}

Even though the basic idea of quantifying edge weights according to the loss of 
information caused by the conversion represented by that edge is straightforward, setting the edge
weights might be all but simple. First of all, the actual amount of information
lost does not only depend on the conversion itself, but also on the (geometric) data
used as input.\footnote{Of course, by the term \emph{loss of information} it is meant the loss of data
in relation to the entire amount of information which an instance of a \emph{source type} provides.}
A conversion from a \emph{Polygon List} to \emph{NURBs} for example, would most
likely drop attributes like texture coordinates. If the \emph{Polygon List} which has been
fed as input to the converter however, did not provide any texture coordinates at all,
the conversion does not really loose this information.
Further, besides the loss of information, other properties of a conversion such as
the (expected) procession time might be considered, when rating a conversion.

It has however turned out, that at least for small conversion graphs a very simple
scheme of assigning edge weights leads to satisfying results.
 \begin{table}[h]
  \begin{tabular}[t]{lll}
  edge weight & type of conversion & examples \\
  \hline
   0 & lossless conversion &  \\
   1 & most conversions  &  \\
   2 & heavily lossy conversions &  \\
  \end{tabular}
  \caption{Assignment of edge weights to conversions as used in \emph{geomagick}.}
  \end{table}


\subsubsection{Shortest Path Problem}

The shortest path problem can be classified into four sub-problems. One is
the, \emph{single pair shortest path problem}, which asks for the the shortest,
path from a given source vertex to one given destination vertex. The problem, in
which the shortest path from one vertex to all vertices in the graph is to be found,
is known as the \emph{single source shortest path problem}. Similarly,in the 
\emph{single destination shortest path problem}, the shortest path from all source
nodes to a given destination vertex has to be found. Further, the problem
in which the shortest path from all nodes to all nodes have to be found, is called
the \emph{all-pairs shortest path problem}.

This subdivision of the shortest path problem helps in finding a well suited algorithm.
In the table \ref{algorithms} below, it is listed for the most important algorithms dealing with the
shortest path problem, which problems they are able to solve.

 \begin{table}[h]
  \begin{tabular}[t]{lll}
  Algorithm & Problems solved & remark\\
  \hline
   Dijkstra & single pair, single source, single destination & \\
   Bellman-Ford & single source & Allows for negative \\ & &
                                 edge weights \\
   A* & single pair & In practice faster than \\ & & 
                      Dijkstra's algorithm\\
   Floyd Warshall & all pairs & \\
  \end{tabular}
  \caption{List of algorithms for solving the shortest path problem}
  \label{algorithms}
\end{table}

% !TODO add a reference ...


\subsection{Evaluation}

The main inconvenience, when using shortest path finding algorithms to find conversion
chains, is certainly that edge values have to be assigned. Even though the practical work
done along with this thesis has shown, that edge weights are easily found when the number
of types is very limited , it remains to be seen whether the assignment of edge weights is
still feasible with larger numbers of types.

Another disadvantage of the model is that it does not consider the fact, that a conversion
chain should try to drop information as late as possible in the chain. An example for that is
depicted in the figure \ref{fig:twochains}. Even though both path from A to D have the same
accumulated weights, the one via C should be preferred. The advantage of the path passing
type C is that the second conversion in the conversion chain still receives double precision
data as input, which might lead to a slightly better result.

\begin{figure}[!ht]
    \begin{center}
        \includegraphics[scale=0.5]{figures/twochains.png}
        \caption{A conversion graph with two shortest paths from Type A to Type D.}
        \label{fig:twochains  }
    \end{center}
\end{figure}

% \subsubsection{Handling Runtime Failiures}


      
